home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 7 / Apprentice-Release7.iso / Environments / PowerLisp 2.01 / Supplemental Documentation / Documentation / Appendix B. Generators and G… < prev    next >
Encoding:
Text File  |  1995-03-23  |  7.4 KB  |  196 lines  |  [TEXT/ROSA]
  1. Common Lisp the Language, 2nd Edition
  2. -------------------------------------------------------------------------------
  3.  
  4. Appendix B.
  5.  
  6. By Crispin Perdue and Richard C. Waters
  7.  
  8. [change_begin]
  9. PREFACE: Generators and gatherers are yet another approach, closely related to
  10. series, to providing iteration in a functional style.
  11.  
  12. The remainder of this chapter consists of a description by Crispin Perdue and
  13. Richard C. Waters of their work on an existing implementation of generators and
  14. gatherers. I have edited the chapter only very lightly to conform to the
  15. overall style of this book. Please see the Preface to this book for more
  16. information about the genesis of the generators/gatherers approach and its
  17. relationship to the work of X3J13.
  18.  
  19.      -Guy L. Steele Jr.
  20.  
  21. [change_end]
  22. -------------------------------------------------------------------------------
  23.  
  24.    *  Introduction
  25.    *  Generators
  26.    *  Gatherers
  27.    *  Discussion
  28.  
  29. -------------------------------------------------------------------------------
  30.  
  31. B.1. Introduction
  32.  
  33. [change_begin]
  34. Generators are generalized input streams in the sense of Smalltalk [20]. A
  35. generator can produce a potentially unbounded number of elements of any type.
  36. Individual elements are not computed until requested by next-in. When an
  37. element is taken from a generator, it is removed by side effect. Subsequent
  38. uses of next-in obtain later elements.
  39.  
  40. There is a close relationship between a generator and a series of the elements
  41. it produces. In particular, any series can be converted into a generator. As a
  42. result, all the scanner functions used for creating series (see appendix A) can
  43. be used to create generators as well. There is no need to have a separate set
  44. of functions for creating generators.
  45.  
  46. Gatherers are generalized output streams. Elements of any type can be entered
  47. into a gatherer using next-out. The gatherer combines the elements together in
  48. time-sequence order into a net result. This result can be retrieved using
  49. result-of.
  50.  
  51. There is a close relationship between a gatherer and a collector function that
  52. combines elements in the same way. In particular, any one-input one-output
  53. collector can be converted into a gatherer. As a result, all the collectors
  54. used for computing summary results from series can be used to create gatherers.
  55. There is no need to have a separate set of functions for creating gatherers.
  56. [change_end]
  57.  
  58. -------------------------------------------------------------------------------
  59.  
  60. B.2. Generators
  61.  
  62. [change_begin]
  63. These functions create and process generators.
  64.  
  65. [Function]
  66. generator series
  67.  
  68. Given a series, generator returns a generator containing the same elements.
  69.  
  70. [Macro]
  71. next-in generator {action}*
  72.  
  73. next-in returns the next element in the generator generator. The actions can be
  74. any Lisp expressions. They are evaluated if and only if no more elements can be
  75. retrieved from generator. If there are no more elements and no actions, it is
  76. an error. It is also an error to apply next-in to a generator a second time
  77. after the generator has run out of elements. As an example of generators,
  78. consider the following.
  79.  
  80. (let ((x (generator (scan '(1 2 3 4)))))
  81.   (with-output-to-string (s)
  82.     (loop (prin1 (next-in x (return)) s)
  83.           (prin1 (next-in x (return)) s)
  84.           (princ "," s))))
  85.  => "12,34,"
  86.  
  87. [change_end]
  88.  
  89. -------------------------------------------------------------------------------
  90.  
  91. B.3. Gatherers
  92.  
  93. [change_begin]
  94. These functions create and process gatherers.
  95.  
  96. [Function]
  97. gatherer collector
  98.  
  99. The collector must be a function of type (function ((series   ))   ). Given
  100. this function, gatherer returns a gatherer that accepts elements of type    and
  101. returns a final result of type   . The method for combining elements used by
  102. the gatherer is the same as the one used by the collector.
  103.  
  104. [Function]
  105. next-out gatherer item
  106.  
  107. Given a gatherer and a value, next-out enters the value into the gatherer.
  108.  
  109. [Function]
  110. result-of gatherer
  111.  
  112. result-of retrieves the net result from a gatherer. result-of can be applied at
  113. any time. However, it is an error to apply result-of twice to the same gatherer
  114. or to apply next-out to a gatherer once result-of has been applied.
  115.  
  116. (let ((g (gatherer #'collect-sum)))
  117.   (dolist (i '(1 2 3 4))
  118.     (next-out g i)
  119.     (if (evenp i) (next-out g (* 10 i))))
  120.   (result-of g))
  121.  => 70
  122.  
  123. [Macro]
  124. gathering ({(var fn)}*) {form}*
  125.  
  126. The first subform must be a list of pairs. The first element of each pair, var,
  127. must be a variable name. The second element of each pair, fn, must be a form
  128. that when wrapped in (function ...) is acceptable as an argument to gatherer.
  129. Each symbol is bound to a gatherer constructed from the corresponding
  130. collector. The body (consisting of the forms) is evaluated in the scope of
  131. these bindings. When this evaluation is complete, gathering returns the
  132. result-of each gatherer. If there are n pairs in the binding list, gathering
  133. returns n values. For example:
  134.  
  135. (defun examp (data)
  136.   (gathering ((x collect) (y collect-sum))
  137.     (iterate ((i (scan data)))
  138.       (case (first i)
  139.         (:slot (next-out x (second i)))
  140.         (:part (dolist (j (second i)) (next-out x j))))
  141.       (next-out y (third i)))))
  142.  
  143. (examp '((:slot a 10) (:part (c d) 40))) => (a c d) and 50
  144.  
  145. As a further illustration of gatherers, consider the following definition for a
  146. simplified version of gathering that handles only one binding pair.
  147.  
  148. (defmacro simple-gathering (((var collector)) &body body)
  149.   `(let ((,var (gatherer (function ,collector))))
  150.      ,@body
  151.      (result-of ,var)))
  152.  
  153. The full capabilities of gathering can be supported in much the same way.
  154. [change_end]
  155.  
  156. -------------------------------------------------------------------------------
  157.  
  158. B.4. Discussion
  159.  
  160. [change_begin]
  161. The idea of generators and gatherers was first proposed by Pavel Curtis. A key
  162. aspect of his proposal was the realization that generators and gatherers can be
  163. implemented simply and elegantly as closures and that these closures can be
  164. compiled very efficiently if certain conditions are met.
  165.  
  166. First, the compiler must support an optimization Curtis calls ``let eversion''
  167. in addition to the optimization methods presented in [45]. If a closure is
  168. created and used entirely within a limited lexical scope, the scopes of any
  169. bound variables nested in the closure can be enlarged (everted) to enclose all
  170. the uses of the closure. This allows the variables to be allocated on the stack
  171. rather than the heap.
  172.  
  173. Second, for a generator/gatherer closure to be compiled efficiently, it must be
  174. possible to determine at compile time exactly what closure is involved and
  175. exactly what the scope of use of the closure is. There are several aspects to
  176. this. The expression creating the generator/gatherer cannot refer to a free
  177. series variable. The generator/gatherer must be stored in a local variable.
  178. This variable must be used only in calls of next-in, next-out, and result-of,
  179. and not inside a closure. In particular the generator/gatherer cannot be stored
  180. in a data structure, stored in a special variable, or returned as a result
  181. value.
  182.  
  183. All of the examples above satisfy these restrictions. For instance, once the
  184. uses of gathering and iterate have been optimized, the body of examp is as
  185. efficient as any loop performing the same computation.
  186.  
  187. The implementation discussed in [52] includes a portable Common Lisp
  188. implementation of generators and gatherers. Although the implementation does
  189. not support optimizations of the kind discussed in [45], it fully optimizes
  190. uses of gathering.
  191. [change_end]
  192.  
  193. -------------------------------------------------------------------------------
  194.  
  195.  
  196.